﻿#define _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
//题目描述：
//给定一个候选人编号的集合 candidates 和一个目标数 target ，
// 找出 candidates 中所有可以使数字和为 target 的组合。
//candidates 中的每个数字在每个组合中只能使用 一次 。
//注意：解集不能包含重复的组合。
int** ptr;
int ptrTop;
int* temp;
int tempTop;
int* EveryLength;
int cmp(const void* p1, const void* p2)
{
    return *(int*)p1 - *(int*)p2;
}
void backtracking(int* nums, int size, int t, int sum, int index)
{
    if (sum >= t)
    {
        if (sum == t)
        {
            int* arr = (int*)malloc(sizeof(int) * 50);
            int j;
            for (j = 0; j < tempTop; j++)
            {
                arr[j] = temp[j];
            }
            ptr[ptrTop] = arr;
            EveryLength[ptrTop] = tempTop;
            ptrTop++;
        }
        return;
    }
    int i;
    for (i = index; i < size; i++)
    {
        if (i > index && nums[i] == nums[i - 1])//剪枝和去重操作
        {
            continue;
        }
        sum += nums[i];
        temp[tempTop++] = nums[i];
        backtracking(nums, size, t, sum, i + 1);
        sum -= nums[i];
        tempTop--;
    }

}
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), cmp);
    ptr = (int**)malloc(sizeof(int*) * 150);
    temp = (int*)malloc(sizeof(int) * 50); EveryLength = (int*)malloc(sizeof(int) * 150);
    int sum = 0, index = 0;
    ptrTop = 0; tempTop = 0;
    backtracking(candidates, candidatesSize,
        target, sum, index);
    *returnSize = ptrTop;
    *returnColumnSizes = (int*)malloc(sizeof(int) * ptrTop);
    int j;
    for (j = 0; j < ptrTop; j++)
    {
        (*returnColumnSizes)[j] = EveryLength[j];
    }
    return ptr;
}